package com.tree;

/**
 * 并查集 : 主要用来对节点进行快速连接,并判断任意两个节点是否相连接
 */
public class UnionFindImpl_1 implements IUnionFind {

    private int[] unionArr; //使用数组下标表示元素,数组值表示关系
    private int count;  //表示元素个数

    /*合并操作
    * 注意两个不同的组别的元素进行合并时,
    *   它们两个分别隶属的小组也要进行合并,
    *   这样它们才是真正的合并
    * */
    @Override
    public void union(int p, int q) {
        int pUnion = find(p);   //找到 p 的组别
        int qUnion = find(q);   //找到 q 的组别
        if (pUnion != qUnion) {
            for (int i = 0; i < count; i++) {
                if (unionArr[i] == qUnion) {
                    unionArr[i] = pUnion;
                }
            }
        }
    }

    @Override
    public int find(int p) {
        assert (p >= 0 && p < count);
        return unionArr[p];
    }

    @Override
    public boolean isConnected(int p, int q) {
        return find(p) == find(q);
    }

    public UnionFindImpl_1(int count) {
        this.count = count;
        unionArr = new int[count];
        //在初始条件下,每个数据都属于不同的组别
        for (int i = 0; i < count; i++) {
            unionArr[i] = i;
        }
    }
}
